/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    let maxMinute = 0;

    for (let row = 0; row < grid.length; row++) {
        for (let column = 0; column < grid[0].length; column++) {
            if (grid[row][column] === 2) {
                // 深度遍历即将腐烂的橘子
                dfs(grid, row, column, 3)
            }
        }
    }

    for (let row = 0; row < grid.length; row++) {
        for (let column = 0; column < grid[0].length; column++) {
            if (grid[row][column] === 1) {
                return -1
            }
            if (grid[row][column] !== 0) {
                maxMinute = Math.max(maxMinute, grid[row][column])
            }
        }
    }

    return maxMinute === 0 ? maxMinute : maxMinute - 2;
};

const dfs = (grid, row, column, minute) => {
    let direction = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    for (let [x, y] of direction) {
        let newRow = row + x,
            newColumn = column + y;

        if (newRow < 0 || newRow >= grid.length || column < 0 || column >= grid[0].length) continue;

        // 如果有橘子，修改节点值为腐烂的时间+2，为什么+2？因为1和2有特殊含义，所以从3开始，return时-2
        if (grid[newRow][newColumn] === 1) {
            grid[newRow][newColumn] = minute
            dfs(grid, newRow, newColumn, minute + 1)
        } else if (grid[newRow][newColumn] !== 0 && grid[newRow][newColumn] > minute) {
            // 深度遍历时，如果左上角为2，那么所有橘子腐烂的时间会有置的值大的情况，所以如果有更小的值，替换一下
            // 同时如果一个岛屿的右下角也为2，从两头开始腐烂，那么腐烂的时间也会相应降低
            grid[newRow][newColumn] = minute
            dfs(grid, newRow, newColumn, minute + 1)
        }
    }
}



grid = [[2,1,1],[1,1,1],[0,1,2]]
// 两次重置时间后输出grid
[ [ 2, 3, 4 ], [ 3, 4, 3 ], [ 0, 3, 2 ] ]
// 如果只有当节点等于1时重置时间后输出grid
[ [ 2, 3, 4 ], [ 7, 6, 5 ], [ 0, 7, 2 ] ]




/**
 * bfs
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    let maxMinute = 0;

    for (let row = 0; row < grid.length; row++) {
        for (let column = 0; column < grid[0].length; column++) {
            if (grid[row][column] === 2) {
                bfs(grid, row, column, 2)
            }
        }
    }

    for (let row = 0; row < grid.length; row++) {
        for (let column = 0; column < grid[0].length; column++) {
            if (grid[row][column] === 1) {
                return -1
            }
            if (grid[row][column] !== 0) {
                maxMinute = Math.max(maxMinute, grid[row][column])
            }
        }
    }

    return maxMinute === 0 ? maxMinute : maxMinute - 2;
};

const bfs = (grid, row, column, minute) => {
    let direction = [[0, 1], [0, -1], [1, 0], [-1, 0]],
        queue = [[row, column]];

    while (queue.length > 0) {
        // 每循环一轮+1，类似二叉树的层序遍历
        minute++
        let len = queue.length;
        while (len-- > 0) {
            let [x, y] = queue.shift()
            for (let [offsetX, offsetY] of direction) {
                let newRow = offsetX + x,
                    newColumn = offsetY + y;

                if (newRow < 0 || newRow >= grid.length || column < 0 || column >= grid[0].length) continue;

                if (grid[newRow][newColumn] === 1) {
                    grid[newRow][newColumn] = minute
                    queue.push([newRow, newColumn])
                } else if (grid[newRow][newColumn] !== 0 && grid[newRow][newColumn] > minute) {
                    grid[newRow][newColumn] = minute
                    queue.push([newRow, newColumn])
                }
            }
        }
    }

}